package com.dzu.hard;

/**
 * @author ZhaoDong
 * @date 2022/12/6 10:49
 * @description 233. 数字 1 的个数
 */
public class Test233 {
    public static void main(String[] args) {
        System.out.println(countDigitOne3(824883294));
    }


    // nb
    // https://leetcode.cn/problems/number-of-digit-one/solution/tong-ge-lai-shua-ti-la-yi-ti-san-jie-bao-ivxe/
    public static int countDigitOne3(int n) {
        // 2021
        int ans = 0;
        for (int i = 1; i <= n; i *= 10) {
            ans += (n / (i * 10)) * i + Math.min(Math.max(n % (i * 10) - i + 1, 0), i);
        }
        return ans;

    }

    // 超内存
    public static int countDigitOne2(int n) {
        int count = 0;
        int[] dp = new int[n + 1];
        dp[1] = 1;
        for (int i = 1; i <= n; i++) {
            dp[i] = dp[i % 10] + dp[i / 10];
            count += dp[i];
        }
        return count;
    }



        // 超时
    public static int countDigitOne(int n) {
        int count = 0;
        while (n > 0) {
            int tempN = n;
            while (tempN > 0) {
                if (tempN % 10 == 1) {
                    count++;
                }
                tempN /= 10;
            }

            n--;
        }
        return count;

    }

}
